/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int maxDepth(struct TreeNode* root)
{
    if(root==NULL)
      return 0;
    int leftDepth=maxDepth(root->left);
    int rightDepth=maxDepth(root->right);
    return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
}

bool isBalanced(struct TreeNode* root)
{
    if(root==NULL)
      return true;
    //return maxDepth(root->left)<maxDepth(root->right)+2&&maxDepth(root->left)+2>maxDepth(root->right)&&isBalanced(root->left)&&isBalanced(root->right);
    return abs(maxDepth(root->left)-maxDepth(root->right))<2&&isBalanced(root->left)&&isBalanced(root->right);
}